//输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。 
//
// 
//
// 示例： 
//
// 
//输入：nums = [1,2,3,4]
//输出：[1,3,2,4] 
//注：[3,1,2,4] 也是正确的答案之一。 
//
// 
//
// 提示： 
//
// 
// 0 <= nums.length <= 50000 
// 0 <= nums[i] <= 10000 
// 
// Related Topics 数组 双指针 排序 👍 192 👎 0

package com.cute.leetcode.editor.cn;
public class DiaoZhengShuZuShunXuShiQiShuWeiYuOuShuQianMianLcof {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7,8,1,2,3,4,7,5,1,2};
        new DiaoZhengShuZuShunXuShiQiShuWeiYuOuShuQianMianLcof().new Solution().exchange(nums);
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 双指针，从两边向中间搜，左指针找偶数，右指针找奇数
         * 注意下标不要越界以及终止条件
         * 考虑程序扩展性，如果是按照正负分，按照能否被x整除分，整体框架是不需要变化的，只需要修改判断条件
         * 可以将条件抽象为一个方法，抽象为方法之后效率下来了，因为每次都需要调用并返回，肯定不如直接位比较
         */
        public int[] exchange(int[] nums) {
            if (nums.length <= 1) return nums;
            int left = 0;
            int right = nums.length-1;
            while (left < right){
                while (left < nums.length && isOdd(nums[left])) left++;
                while (right >= 0 && !isOdd(nums[right])) right--;
                if (left >= right) break;
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                left++;
                right--;
            }
            return nums;
        }
        public boolean isOdd(int num){
            return (num & 1) == 1;
        }
        public boolean isPositive(int num){
            return num > 0;
        }
        public boolean canBeDividedBy3(int num){
            return num % 3 == 0;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}